1. Field of the Invention
The present invention generally relates to number theory, and more particularly to a method of partitioning a set of numbers to find an optimal solution.
2. Description of the Related Art
Number partitioning is one of the most basic problems in combinational optimization: it seeks to divide a set S of n positive numbers across a set of k mutually exclusive and collectively exhaustive subsets <S1, S2, . . . , Sk> so as to minimize the sum of the largest set. For instance, given the set of integers {5, 4, 3, 2, 1}, the 3-way partitioning <{5}, {4, 1}, {3, 2}> is an optimal solution that perfectly balances all subsets to an equal sum of 5. Despite its simplicity, number partitioning is nevertheless “NP-complete” (nondeterministic polynomial time) and is often used to prove the NP-completeness of other quantitative reasoning problems, e.g., bin packing, knapsack, etc. Real-world applications and extensions of number partitioning are numerous, including multi-processor scheduling, machine reassignment, and voting manipulation. Hence, efficient methods to determine optimal solutions are of particular interest in the broader scope of combinatorial search.
One of the easiest approaches to number partitioning is a heuristic known as the greedy algorithm which can quickly produce high-quality (albeit suboptimal) solutions. According to the greedy algorithm, the numbers in the set are sorted by size in decreasing order, and each one is incrementally assigned to the partition whose size is currently the smallest. This approach can be modified to compute optimal solutions by incorporating backtracking: each assignment of a number to a partition creates a different branch in search, and all possible combinations of assignments are attempted in order to produce the one with minimal cost. By extending this depth-first framework with branch-and-bound pruning techniques and symmetry breaking, one arrives at the complete greedy algorithm (CGA).
An alternative greedy heuristic referred to as KK (after Karmarkar-Karp) constructs solutions in an entirely different way. Rather than committing each number to a specific partition, it instead considers potential pairings based on set differences. In each iteration of the algorithm, the two largest numbers are extracted from the set, and replaced by their absolute difference. In doing so, the numbers (or more generally, the subsets containing them) are ensured to be assigned to different partitions. The ultimate arrangement of these subsets is not finalized until the list is fully processed. A complete extension to this heuristic exists as well (the complete Karmarkar-Karp algorithm, or CKK). The additional branches in this variation correspond to set unions, where numbers are joined rather than assigned to exclusive subsets. For k=2, CKK performs dramatically faster than CGA (especially in the presence of perfect partitions) and can be further improved by pruning certain leaf nodes. However, due to the high overhead and bookkeeping required, CKK is less effective for large values of k.
In CGA, each number Si is committed to a specific subset before the assignment of any subsequent numbers are processed. A radically different approach is taken by the methodology referred to as recursive number partitioning (RNP), in which a complete set of members for a range of partitions is constructed (and partitioned) before considering the members of subsequent partitions. If k is even, the set of partitions may be divided in half, and each individual number can be assigned to one half or the other. If k is odd, the partitions may be divided into S1 and [S2, Sk]. In order to explore the space of all possible arrangements, an inclusion-exclusion tree is searched. An internal node of this tree may be pruned if a partial subset cannot possibly extend to a better solution. The leaves of this tree correspond to coarse decompositions of numbers to subproblems, but not necessarily to assignments within each group. To construct solutions, optimal partitions are obtained for each subproblem, and combined if their concatenation results in an improved solution. Subproblems are solved in the same way; only in the base case (where k=2) is traditional two-way partitioning employed. For certain values of n and k, RNP is several orders of magnitude faster than CGA.
The basic framework of RNP has recently been enhanced in two fundamental ways to produce the improved recursive number partitioning (IRNP) algorithm. First, the inclusion-exclusion tree is replaced by an extension of the Schroeppel/Shamir algorithm that more effectively searches the space of viable subset sums. This new approach divides the set of numbers in half and enumerates all possible subsets in each division. Although this algorithm requires exponential memory, it allows very fast exploration of satisficing sums simply by iterating through the two halves in tandem. Second, the solver makes calls to CGA (or CKK) for small n, since these problems tend to be more amenable to the original search space.